package com.feiyue.learning.sort;

import java.util.Arrays;

/**
 * 快速排序
 * @author  feiyue
 * @date  2020/3/29
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] data = new int[]{8, 8, 8, 8, 8};

        System.out.print("排序前: ");
        Arrays.stream(data).forEach(r->System.out.print(r + " "));

        quickSort(data, 0, data.length - 1);

        System.out.print("\n排序后: ");
        Arrays.stream(data).forEach(r->System.out.print(r + " "));
    }

    private static void quickSort(int[] data, int low, int high) {
        if (low >= high) {
            return;
        }

        int index = adjustDataV3(data, low, high);
        quickSort(data, low, index - 1);
        quickSort(data, index + 1, high);
    }

    private static int adjustData(int[] data, int low, int high) {
        int baseValue = data[low];
        int left = low;
        int right = high + 1;

        while (true) {

            // 先++, 当遇到等于基准值的时候, 指针还是会往前走
            while (data[++left] < baseValue) {
                if (left == high) break;
            }

            while (data[--right] > baseValue) {
                if (right == low) break;
            }

            if (left >= right) break;
            exchange(data, left, right);
        }
        exchange(data, low, right);
        return right;
    }

    private static int adjustDataV2(int[] data, int low, int high) {
        int baseValue = data[low];
        int left = low + 1;
        int right = high;

        while (true) {

            // 从左往右遍历需要跳过基准数据
            while (left < high && data[left] < baseValue) {
                left++;
            }

            // 从右往左, 可能会取到基准值(right==low), 这个时候不要交换
            while (right > low && data[right] > baseValue) {
                right--;
            }

            if (left >= right || right == low) break;

            // ++/-- 为了避免左右同时遇到等于基准值出现死循环
            exchange(data, left++, right--);
        }
        exchange(data, low, right);
        return right;
    }

    private static int adjustDataV3(int[] data, int low, int high) {
        int baseValue = data[low];
        int left = low;
        int right = high;

        while (left != right) {

            // 先从右边进行, 避免基准值最小时, 从左开始出现问题
            while (data[right] >= baseValue && right > left) {
                right--;
            }

            while (data[left] <= baseValue && left < right) {
                left++;
            }

            if (right > left) {
                exchange(data, left, right);
            }
        }
        exchange(data, low, left);
        return left;
    }

    private static void exchange(int[] data, int left, int right) {
        int temp = data[left];
        data[left] = data[right];
        data[right] = temp;
    }
}
